class A_SEARCH{ETP,ATP<$ARR{ETP}} |
---|
**** | Searching algorithms on arrays. Note that the element comparison is defined here bu the percondition checks may use a different lt when calling the is_sorted routine in A_SORT |
COMPARE{_} |
binary_search(a: ATP,e: ETP): INT |
---|
binary_search(a: ATP,e:ETP,l,u: INT):INT |
---|
**** | Assuming self is sorted, return the index of the element preceding the first element greater than `e' according to `elt_lt' in the range [l,u]. -1 if all elements are greater than `e'. |
binary_search(a: ATP,e:ETP,lt: ROUT{ETP,ETP}:BOOL,l,u: INT):INT |
---|
**** | Assuming self is sorted, return the index of the element preceding the first element greater than `e' according to `elt_lt' in the range [l,u]. -1 if all elements are greater than `e'. |
elt_eq(e1,e2:ETP):BOOL .. Included as elt_eq |
---|
**** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
elt_hash(e:ETP):INT .. Included as elt_hash |
---|
**** | A hash value associated with an element. Must have the property that if "elt_eq(e1,e2)" then "elt_hash(e1)=elt_hash(e2)". Can be defined to always return 0, but many routines will then become quadratic. Uses object "id" by default. May be redefined in descendants. |
elt_lt(e1,e2:ETP):BOOL .. Included as elt_lt |
---|
**** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
elt_nil: ETP .. Included as elt_nil |
---|
**** | Return the nil value. If the element is under $NIL then return e.nil. Otherwise, return void
_ |
index_if(a: ATP,test:ROUT{ETP}:BOOL):INT |
---|
**** | Return the index of the leftmost element that satisfies `test', or -1 if there is none. |
index_of(a: ATP, e: ETP): INT |
---|
**** | Return the index of the elemetn 'e' in 'a' Return -1 if the element is not found. Does not assume a is sorted |
is_elt_nil(e:ETP):BOOL .. Included as is_elt_nil |
---|
match_subarray(a: ATP, marr:ARRAY{ETP},l,u: INT):INT |
---|
**** | The index of the leftmost subarray of marr which matches 'a' Confine search to subrange [l,u] of a -1 if none. Uses simple algorithm which has good performance unless the arrays are special (eg. many repeated values). Also uses ARRAY{ETP} rather than a general $ARR since it will almost certainly be worthwhile to copy into a concrete class rather than use dispatching on the argument |
check_range(a: ATP,l,u: INT): BOOL |
---|
is_sorted(a: ATP,l,u:INT): BOOL |
---|